Topological Sort

Definition / 释义

Topological sort（拓扑排序）：一种对有向无环图（DAG, Directed Acyclic Graph）中的节点进行线性排序的方法，使得对每一条有向边 u → v，节点 u 都排在 v 之前。
常用于任务依赖与先后顺序约束的问题，例如课程先修关系、构建/编译依赖、工作流调度等。（若图中存在环，则不存在有效的拓扑排序。）

Pronunciation / 发音（IPA）

/ˌtɑːpəˈlɑːdʒɪkəl sɔːrt/（美式常见）

Etymology / 词源

Topological 源自 topology（拓扑学）：研究“连接关系/结构”而非具体距离形状的数学分支；在图论语境中强调“节点之间的关系结构”。
Sort 表示“排序”。合起来即“按依赖结构进行排序”。该术语在计算机科学中常用于图算法与依赖管理。

Examples / 例句

To build the project, we run a topological sort of the modules to respect dependencies.
为了构建这个项目，我们对各模块做拓扑排序，以遵守依赖关系。

Given course prerequisites, a topological sort can produce an ordering that lets you take each class only after its prerequisites.
给定课程的先修要求，拓扑排序可以生成一种顺序，确保你每门课都在满足先修课之后再修读。

Related Words / 相关词汇

• DAG
• Graph
• Dependency
• Prerequisite
• Cycle
• Acyclic
• Kahn’s Algorithm
• Depth-First Search

Notable Works / 典型出处（常见出现的著作/资料）

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；常简称 CLRS）：在图算法章节中讨论拓扑排序及其与 DFS 的关系。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在有向图与任务调度相关内容中介绍拓扑排序。
• The Algorithm Design Manual（Steven S. Skiena）：在图与调度/依赖类问题中提及拓扑排序作为基础工具。
• 经典图论与算法课程讲义（如大学数据结构/算法课程的 DAG、依赖解析与调度单元）也常将其作为核心概念。